This patent application builds upon a public-key identification scheme presented in the 2011 paper by Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari, entitled “Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials,” available at https://www.iacr.org/archive/crypto2011/68410703/68410703.pdf, which is referred to herein as “Sakumoto.”
A trusted computing base (TCB) of a computer system has been described as “the set of all hardware, firmware, and/or software components that are critical to its security, in the sense that bugs or vulnerabilities occurring inside the TCB might jeopardize the security properties of the entire system. By contrast, parts of a computer system outside the TCB must not be able to misbehave in a way that would leak any more privileges than are granted to them in accordance to the security policy.
The careful design and implementation of a system's trusted computing base is paramount to its overall security . . . . Modern operating systems strive to reduce the size of the TCB so that an exhaustive examination of its code base (by means of manual or computer-assisted software audit or program verification) becomes feasible.” (Source: https://en.wikipedia.org/wiki/Trusted_computing_base, visited Aug. 25, 2016.)
Security of the TCB can be implemented via a “chain of trust.” A chain of trust is established by validating each layer of hardware and software, beginning with the hardware and iteratively validating each firmware and software component that is loaded into memory. A chain of trust is typically established during a boot of the computer system. The chain of trust begins with a trust anchor, such as the hardware of the computing system, which is trusted because the hardware will only boot from firmware or software that is digitally signed. A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, that the sender cannot deny having sent the message (authentication and non-repudiation), and that the message was not altered in transit (integrity).
The signing authority for firmware and/or software will only sign boot programs that enforce security, such as only running programs that are themselves signed, or only allowing signed code to have access to certain features of the computing system. The establishment of a chain of trust may continue through several software layers. Each component of a computing system assumes trust of its predecessor component (i−1) and measures the integrity of its successor component (i+1) before relinquishing control to the successor component. This process repeats iteratively until all components of the computing system's code base are trusted.
The validation that occurs as each component of the TCB is loaded into memory depends upon the security of the digital signatures of the components. Digital signature schemes are typically based on public key (asymmetric) cryptography which uses pairs of keys. In a key pair, the public key, which may be disseminated widely, is paired with a private key, which is known only to the owner. The authenticity of a signature generated from a fixed message and fixed private key can be verified by using the corresponding public key.
A digital signature scheme typically consists of three algorithms: (1) A key generation algorithm selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key. (2) A signing algorithm receives a message and a private key and produces a digital signature. A recipient of the message uses the public key to authenticate that the message originated with a holder of the paired private key. (3) A signature verifying algorithm receives a message, public key and signature, and either accepts or rejects the message's claim to authenticity (i.e., that the message originated with a holder of the paired private key).
Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in practice by any adversary. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means. For example, public key cryptography is based upon the assumption that it is computationally infeasible to generate a valid signature for a party without knowing that party's private key.
The security of public key cryptographic systems is based upon the computational infeasibility of certain mathematical calculations. For example, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to prime numbers, the process is called prime factorization. Integer factorization is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes).
By comparison, a quantum computer could efficiently solve the prime factorization problem using, for example, an algorithm such as Shor's algorithm to find the prime factors of a given integer. This ability would allow a quantum computer to decrypt many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers or the discrete logarithm problem, both of which can be solved by Shor's algorithm. In particular, the RSA, Diffie-Hellman, and Elliptic curve Diffie-Hellman algorithms could be broken. These algorithms are currently used to protect secure Web pages, encrypted email, and many other types of data. Breaking these algorithms would have significant ramifications for electronic privacy and security.